{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Size Subarray Sum Equals k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubArrayLen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和等于 k 的最长子数组长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组 <code><em>nums</em></code> 和一个目标值 <code><em>k</em></code>，找到和等于<em> <code>k</code> </em>的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 <code>0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><em>nums</em> = <code>[1,-1,5,-2,3]</code>, <em>k</em> = <code>3</code>\n",
    "<strong>输出: </strong>4 \n",
    "<strong>解释: </strong>子数组 <code>[1, -1, 5, -2]</code> 和等于 3，且长度最长。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><em>nums</em> = <code>[-2,-1,2,1]</code>, <em>k</em> = <code>1</code>\n",
    "<strong>输出: </strong>2 <strong>\n",
    "解释: </strong>子数组<code> [-1, 2]</code> 和等于 1，且长度最长。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-size-subarray-sum-equals-k](https://leetcode.cn/problems/maximum-size-subarray-sum-equals-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-size-subarray-sum-equals-k](https://leetcode.cn/problems/maximum-size-subarray-sum-equals-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-1,5,-2,3]\\n3', '[-2,-1,2,1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct = {}\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        dct[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in dct and i - dct[pre - k] > ans:\n",
    "                ans = i - dct[pre - k]\n",
    "            if pre not in dct:\n",
    "                dct[pre] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum = 0\n",
    "        d = {0:-1}\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre_sum += nums[i]\n",
    "            if pre_sum == k:\n",
    "                ans = i + 1\n",
    "            elif pre_sum - k in d:\n",
    "                ans = max(ans, i - d[pre_sum-k])\n",
    "            if pre_sum not in d:\n",
    "                d[pre_sum] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Prefix sum. Time O(n) Space O(n)\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        curSum = 0\n",
    "        # sum of a[0]...a[i], i.e. the first i elems: i\n",
    "        prefix = {0: 0}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            if curSum - k in prefix.keys():\n",
    "                # prefix[curSum - k]: j, means sum of the first j elems, i.e. a[0]...a[j-1], is prefix[curSum - k]\n",
    "                # sum of a[j]...a[i] is k. Length of the array is i - j + 1\n",
    "                res = max(res, i - prefix[curSum - k] + 1)\n",
    "            if curSum not in prefix.keys():\n",
    "                # curSum is the sum of the first i + 1 elems\n",
    "                prefix[curSum] = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefixsum=0\n",
    "        result=0\n",
    "        foundvalue={}\n",
    "        foundvalue[0]=-1\n",
    "        for i in range(len(nums)):\n",
    "            prefixsum+=nums[i]\n",
    "            if prefixsum not in foundvalue:\n",
    "                foundvalue[prefixsum]=i\n",
    "            if prefixsum-k in foundvalue:\n",
    "                result = max(result, i-foundvalue[prefixsum-k])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        #不能用滑窗,因为有负数\n",
    "        #哈希+前缀和,因为要求子数组最长,相同前缀和只保留最早的一个\n",
    "        to={0:-1}\n",
    "        pre,ans=0,0\n",
    "        for i,x in enumerate(nums):\n",
    "            pre+=x\n",
    "            if pre-k in to:\n",
    "                ans=max(ans,i-to[pre-k])\n",
    "            if pre not in to:\n",
    "                to[pre]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:   \n",
    "        f = {}\n",
    "        f[0] = -1\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            presum += nums[i]\n",
    "            if presum - k in f:\n",
    "                ans = max(ans, i - f[presum - k])\n",
    "            \n",
    "            if presum not in f:\n",
    "                f[presum] = i\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        dp={0:-1}\n",
    "        ret=0\n",
    "        for i in range(len(nums)):\n",
    "            count+=nums[i]\n",
    "            if count not in dp:\n",
    "                dp[count]=i\n",
    "            if count-k in dp:\n",
    "                ret=max(ret,i-dp[count-k])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix = {0: -1}\n",
    "        cur_total = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur_total += nums[i]\n",
    "            if cur_total - k in prefix:\n",
    "                ans = max(ans, i - prefix[cur_total - k])\n",
    "            if cur_total not in prefix:\n",
    "                prefix[cur_total] = i\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # res = 0\n",
    "        # dic = {}\n",
    "        # for i in range(n):\n",
    "        #     # SUM = 0\n",
    "        #     for j in range(i,n):\n",
    "        #         t = k - nums[j]\n",
    "        #         if t in dic:\n",
    "        #             res = max(res, dic[t]+1)\n",
    "        #         dic[t] = j-i\n",
    "        #         # SUM += nums[j]\n",
    "        #         # if SUM == k:\n",
    "        #         #     res = max(res,j-i+1)\n",
    "        # return res\n",
    "        \n",
    "        # res = 0\n",
    "        # prefix = [0]*(n+1)\n",
    "        # for i in range(n):\n",
    "        #     prefix[i+1] = prefix[i]+nums[i]\n",
    "        # for i in range(n+1):\n",
    "        #     for j in range(i,n+1):\n",
    "        #         if prefix[j]-prefix[i]==k:\n",
    "        #             res = max(res, j-i)\n",
    "        # return res\n",
    "\n",
    "        res = 0\n",
    "        dic = {}\n",
    "        dic[0] = -1\n",
    "        prefix = 0\n",
    "        for i in range(n):\n",
    "            prefix += nums[i]\n",
    "            t = prefix - k\n",
    "            if t in dic:\n",
    "                res = max(res, i-dic[t])\n",
    "            if prefix not in dic:\n",
    "                dic[prefix] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        lookup = {}\n",
    "        cur_len, res = 0, 0\n",
    "        prefix_sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix_sum += nums[i]\n",
    "            if prefix_sum == k:\n",
    "                res = i + 1\n",
    "            elif prefix_sum - k in lookup:\n",
    "                res = max(res, i - lookup[prefix_sum-k])\n",
    "            if prefix_sum not in lookup:\n",
    "                lookup[prefix_sum] = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        psumdict = {}\n",
    "        cursum = 0\n",
    "        ans = 0\n",
    "        psumdict[0] = -1 \n",
    "        for index, num in enumerate(nums):\n",
    "            cursum += num\n",
    "            if cursum not in psumdict:\n",
    "                psumdict[cursum] =  index\n",
    "            if cursum - k in psumdict:\n",
    "                ans = max(ans, index - psumdict[cursum - k] )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        hashmap = {}\n",
    "        running_sum = 0\n",
    "        hashmap[0] = -1\n",
    "        max_len = 0\n",
    "        \n",
    "        for index, num in enumerate(nums):\n",
    "            running_sum += num\n",
    "            if running_sum - k in hashmap:\n",
    "                max_len = max(max_len, index - hashmap[running_sum - k])\n",
    "            if running_sum not in hashmap:\n",
    "                hashmap[running_sum] = index\n",
    "                \n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        m = dict()\n",
    "        sums = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            sums += nums[i]\n",
    "\n",
    "            if sums - k in m:\n",
    "                ans = max(ans, i - m[sums - k])\n",
    "\n",
    "            if sums == k:\n",
    "                ans = max(ans, i + 1)\n",
    "\n",
    "            if sums not in m:\n",
    "                m[sums] = i\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum_dict = {0: -1}\n",
    "        accumulate_val = 0\n",
    "        candidates = []\n",
    "\n",
    "        for i, val in enumerate(nums):\n",
    "            accumulate_val += val\n",
    "            need_val = accumulate_val - k\n",
    "            if need_val in pre_sum_dict:\n",
    "                candidates.append(i - pre_sum_dict[need_val])\n",
    "            if not accumulate_val in pre_sum_dict:\n",
    "                pre_sum_dict[accumulate_val] = i\n",
    "        \n",
    "        if candidates:\n",
    "            return max(candidates)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # prefixsum + hashtable\n",
    "        prefixsum = 0\n",
    "        length = 0  \n",
    "        indices = {} #store the value of prefixsum and its index\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            prefixsum += nums[i]\n",
    "            if prefixsum not in indices.keys():\n",
    "                indices[prefixsum] = i #key is the prefixsum, value is the index\n",
    "\n",
    "            if prefixsum == k:  #数组从0到i的和等于k\n",
    "                length = i+1\n",
    "            if prefixsum - k in indices.keys():\n",
    "                length = max(length, i - indices[prefixsum - k]) #数组从indices[prefixsum - k]+1 到i 的和等于k\n",
    "\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        '记录prefix和prefix的下标，如果遇到prefix-k在dict中说明 prefix[j]-prefix[i] = k'\n",
    "\n",
    "        dic = {0:-1}    # {prefix: idx}\n",
    "        max_len = prefix = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if prefix - k in dic and i - dic[prefix - k] > max_len:\n",
    "                max_len = i - dic[prefix - k]\n",
    "            if prefix not in dic:\n",
    "                dic[prefix] = i\n",
    "        return max_len\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:   \n",
    "        hashmap = {0: -1}            # f(value) = idx\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            presum += num\n",
    "            if presum - k in hashmap:\n",
    "                ans = max(ans, i - hashmap[presum - k])\n",
    "        \n",
    "            if presum not in hashmap:\n",
    "                hashmap[presum] = i\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # dic stores prefix_sums of subarrays ending at some pos i and starting at the head\n",
    "        dic = {0: -1}\n",
    "        temp = 0\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp += nums[i]\n",
    "            if temp - k in dic:\n",
    "                result = max(result, i - dic[temp - k])\n",
    "            if temp not in dic:\n",
    "                dic[temp] = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum = {0: -1}\n",
    "        accumulate_val = 0\n",
    "        ret_val = 0\n",
    "        for idx, val in enumerate(nums):\n",
    "            accumulate_val += val\n",
    "            need_pre_val = accumulate_val - k\n",
    "            if need_pre_val in pre_sum:\n",
    "                ret_val = max(idx - pre_sum[need_pre_val], ret_val)\n",
    "            if accumulate_val not in pre_sum:\n",
    "                pre_sum[accumulate_val] = idx\n",
    "        return ret_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        mp = {0: -1}\n",
    "        sum = 0\n",
    "        maxLen = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "            if sum == k:\n",
    "                maxLen = i + 1\n",
    "            elif sum - k in mp:\n",
    "                maxLen = max(maxLen, i - mp[sum - k])\n",
    "            if sum not in mp:\n",
    "                mp[sum] = i\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        '记录prefix和prefix的下标，如果遇到prefix-k在dict中说明 prefix[j]-prefix[i] = k'\n",
    "\n",
    "        dic = {0:-1}\n",
    "        max_len = prefix = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if prefix - k in dic and i - dic[prefix - k] > max_len:\n",
    "                max_len = i - dic[prefix - k]\n",
    "            if prefix not in dic:\n",
    "                dic[prefix] = i\n",
    "        return max_len\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix = {}\n",
    "        prefix[0] = 0\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            if (s - k) in prefix.keys():\n",
    "                ans = max(ans, i + 1 - prefix[s - k])\n",
    "            if s not in prefix.keys():\n",
    "                prefix[s] = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        # right_sum - left_sum = k\n",
    "        # right_sum - k = left_sum\n",
    "\n",
    "        # 利用prefix\n",
    "        # -----------------\n",
    "        # | prefix - k | k |\n",
    "        # | prefix         | \n",
    "\n",
    "        # nums     1  1 -1 5 -2 3\n",
    "        # prefix   0  1 2  1 6  4 7\n",
    "        #          -1 0 1 过 3  4 5 \n",
    "        # 最开始加入0的目的：表示空前缀，当total刚好=k时，确保没有差的   \n",
    "        prefix = {0: -1}\n",
    "        cur_total = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur_total += nums[i]\n",
    "            # 寻找max size\n",
    "            if cur_total - k in prefix:\n",
    "                ans = max(ans, i - prefix[cur_total - k])\n",
    "            # 找最大：只记录一个数第一次出现的位置\n",
    "            if cur_total not in prefix:\n",
    "                prefix[cur_total] = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        preSum = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            preSum[i] = preSum[i - 1] + nums[i - 1]\n",
    "\n",
    "        hashmap = {}\n",
    "\n",
    "        res = 0 \n",
    "        for i in range(n + 1):\n",
    "            if preSum[i] not in hashmap:\n",
    "                hashmap[preSum[i]] = i\n",
    "            if (j := preSum[i] - k) in hashmap:\n",
    "                res = max(res, i - hashmap[j])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # nums, k = [4,1,1,1,1,2], 4\n",
    "        pre = 0\n",
    "        dic = {0: -1}\n",
    "        max_len = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            pre += num\n",
    "            if pre - k in dic:\n",
    "                max_len = max(max_len, i - dic[pre - k])\n",
    "            if pre not in dic: # 记录第一次出现的位置\n",
    "                dic[pre] = i\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct = dict()\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        dct[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in dct and i - dct[pre - k] > ans:\n",
    "                ans = i - dct[pre - k]\n",
    "            if pre not in dct:\n",
    "                dct[pre] = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum = 0\n",
    "        longest_subarray = 0\n",
    "        indices = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix_sum += num \n",
    "            \n",
    "            # 检查是否存在累加和等于k的子数组\n",
    "            if prefix_sum == k:\n",
    "                longest_subarray = i + 1\n",
    "                \n",
    "            # 如果之前出现过累加和等于prefix_sum - k的位置\n",
    "            # 则更新最长子数组长度\n",
    "            if prefix_sum - k in indices:\n",
    "                longest_subarray = max(longest_subarray, i - indices[prefix_sum - k])\n",
    "                \n",
    "            # 仅当当前前缀和不在字典中时，将其添加到字典中\n",
    "            if prefix_sum not in indices:\n",
    "                indices[prefix_sum] = i\n",
    "        \n",
    "        return longest_subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        summap = {0: -1}\n",
    "        for i, num in enumerate(nums):\n",
    "            presum += num\n",
    "            if presum - k in summap:\n",
    "                ans = max(ans, i - summap[presum - k])\n",
    "            if presum not in summap:\n",
    "                summap[presum] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSum = 0\n",
    "        hashtable = {0:-1}\n",
    "        maxLen = 0\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            preSum += num\n",
    "            if preSum - k in hashtable:\n",
    "                maxLen = max(i-hashtable[preSum - k], maxLen)\n",
    "            if preSum not in hashtable:\n",
    "                hashtable[preSum] = i\n",
    "            \n",
    "        return maxLen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 联系的\n",
    "        m = {0: -1}\n",
    "        s = ans = 0\n",
    "        for i, c in enumerate(nums):\n",
    "            s += c\n",
    "            if s - k in m:\n",
    "                ans = max(ans, i - m[s-k])\n",
    "            if s not in m:\n",
    "                m[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        my_dict = dict()\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        my_dict[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre +=nums[i]\n",
    "            if pre - k in my_dict and i-my_dict[pre-k] > ans:\n",
    "                ans = i - my_dict[pre-k]\n",
    "            if pre not in my_dict:\n",
    "                my_dict[pre] = i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum=0\n",
    "        longest_subarray=0\n",
    "        indices={}\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix_sum+=num\n",
    "\n",
    "            if prefix_sum == k:\n",
    "                longest_subarray = i+1\n",
    "            \n",
    "            if prefix_sum-k in indices:\n",
    "                longest_subarray = max(longest_subarray, i-indices[prefix_sum-k])\n",
    "            \n",
    "            if prefix_sum not in indices:\n",
    "                indices[prefix_sum]=i\n",
    "\n",
    "        return longest_subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        preSum = collections.defaultdict()\n",
    "        preSum[0] = 0\n",
    "        cur = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            cur += nums[i]\n",
    "            if cur not in preSum:\n",
    "                preSum[cur] = i + 1\n",
    "\n",
    "            if cur - k in preSum:\n",
    "                ans = max(i - preSum[cur-k] + 1, ans)\n",
    "            \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct=dict()\n",
    "        n=len(nums)\n",
    "        pre=0\n",
    "        dct[0]=-1\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            pre+=nums[i]\n",
    "            if pre-k in dct and i-dct[pre-k]>ans:\n",
    "                ans=i-dct[pre-k]\n",
    "            if pre not in dct:\n",
    "                dct[pre]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        s = 0\n",
    "        cache = {0: -1}\n",
    "        for i, n in enumerate(nums):\n",
    "            s += n\n",
    "            if s - k in cache:\n",
    "                res = max(res, i - cache[s - k])\n",
    "            # s不在cache里时才更新\n",
    "            if s not in cache:\n",
    "                cache[s] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cumsum = [0] * (n+1)\n",
    "        pos = {}\n",
    "        ans = 0\n",
    "        pos[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            cumsum[i] = cumsum[i-1] + nums[i-1]\n",
    "            if cumsum[i] not in pos:\n",
    "                pos[cumsum[i]] = i\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            oppo = cumsum[i]-k\n",
    "            if oppo in pos:\n",
    "                ans = max(ans, i-pos[oppo])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        dp = {0:-1}\n",
    "        c = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            c += num\n",
    "            if c - k in dp:\n",
    "                ans = max(ans, i-dp[c-k])\n",
    "            if c not in dp:\n",
    "                dp[c] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        sums = [0] * n\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                sums[0] = nums[0]\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + nums[i]\n",
    "            \n",
    "            if sums[i] - k in dist:\n",
    "                res = max(res, i - dist[sums[i] - k])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix = [0] * (len(nums)+1)\n",
    "        curval = 0\n",
    "        for i in range(len(nums)):\n",
    "            curval += nums[i]\n",
    "            prefix[i+1] = curval\n",
    "        lookup = {}\n",
    "        ans = 0\n",
    "        for id, num in enumerate(prefix):\n",
    "            if (num - k) in lookup.keys():\n",
    "                ans = max(ans, id - lookup[num-k])\n",
    "            if num not in lookup:\n",
    "                lookup[num] = id\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for i, j in enumerate(acc):\n",
    "            if j - k in cnt:\n",
    "                ans = max(ans, i - cnt[j - k]) \n",
    "            if j in cnt:\n",
    "                continue\n",
    "            cnt[j] = i \n",
    "        return ans \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum = 0\n",
    "        longest_subarray = 0\n",
    "        indices = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix_sum += num \n",
    "            \n",
    "            # 检查是否存在累加和等于k的子数组\n",
    "            if prefix_sum == k:\n",
    "                longest_subarray = i + 1\n",
    "                \n",
    "            # 如果之前出现过累加和等于prefix_sum - k的位置\n",
    "            # 则更新最长子数组长度\n",
    "            if prefix_sum - k in indices:\n",
    "                longest_subarray = max(longest_subarray, i - indices[prefix_sum - k])\n",
    "                \n",
    "            # 仅当当前前缀和不在字典中时，将其添加到字典中\n",
    "            if prefix_sum not in indices:\n",
    "                indices[prefix_sum] = i\n",
    "        \n",
    "        return longest_subarray\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        #不能用滑窗,因为有负数\n",
    "        #哈希+前缀和,因为要求子数组最长,相同前缀和只保留最早的一个\n",
    "        to={0:-1}\n",
    "        pre,ans=0,0\n",
    "        for i,x in enumerate(nums):\n",
    "            pre+=x\n",
    "            if pre-k in to:\n",
    "                ans=max(ans,i-to[pre-k])\n",
    "            if pre not in to:\n",
    "                to[pre]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        preSum = 0\n",
    "        h = {}\n",
    "        h[0] = -1\n",
    "        ans = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            preSum += num\n",
    "            if preSum - k in h:\n",
    "                ans = max(ans, right - h.get(preSum - k))\n",
    "            if preSum not in h:\n",
    "                h[preSum] = right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cumsum = [0] * (n+1)\n",
    "        pos = {}\n",
    "        ans = 0\n",
    "        pos[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            cumsum[i] = cumsum[i-1] + nums[i-1]\n",
    "            if cumsum[i] not in pos:\n",
    "                pos[cumsum[i]] = i\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if cumsum[i]-k in pos:\n",
    "                ans = max(ans, i-pos[cumsum[i]-k])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        dic = {0:-1}\n",
    "        cur = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            cur += num\n",
    "            # if cur == k:\n",
    "            #     res = i + 1\n",
    "            if cur - k in dic:\n",
    "                res = max(res, i - dic[cur - k])\n",
    "            if cur not in dic:\n",
    "                dic[cur] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSums = {0: -1}\n",
    "        curPreSum = 0\n",
    "        maxLen = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            curPreSum += num\n",
    "            target = curPreSum - k\n",
    "            \n",
    "            if target in preSums:\n",
    "                maxLen = max(maxLen, idx - preSums[target])\n",
    "            if curPreSum not in preSums:\n",
    "                preSums[curPreSum] = idx\n",
    "        \n",
    "        return maxLen\n",
    "\n",
    "'''\n",
    "k = 3\n",
    "[1,2,1]\n",
    "\n",
    "preSums = {0:0, 1:0}\n",
    "1, 2\n",
    "3, 0\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSum = dict()\n",
    "        preSum[0] = -1\n",
    "        presum = [0]\n",
    "        s = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s += v\n",
    "            presum.append(s)\n",
    "            if s not in preSum:\n",
    "                preSum[s] = i\n",
    "        res = 0\n",
    "        for p in range(len(nums), -1, -1):\n",
    "            if presum[p] - k in preSum:\n",
    "                res = max(res, p - preSum[presum[p] - k]-1)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        cumsum = [0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cumsum.append(cumsum[-1]+nums[i])\n",
    "        record = defaultdict(int)\n",
    "        max_length = 0\n",
    "        record[0] = 0\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if cumsum[i]-k in record:\n",
    "                max_length = max(max_length, i-record[cumsum[i]-k])\n",
    "            if cumsum[i] not in record:\n",
    "                record[cumsum[i]] = i\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre = list(accumulate(nums, initial = 0))\n",
    "        n = len(nums)\n",
    "        m = {}\n",
    "        m[0] = -1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            v = pre[i + 1]\n",
    "            d = v - k\n",
    "            if nums[i] == k:\n",
    "                res = max(res, 1)\n",
    "            if d in m:\n",
    "                res = max(res, i - m[d])\n",
    "            if v not in m:\n",
    "                m[v] = i\n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        hashmap = {}\n",
    "        running_sum = 0\n",
    "        hashmap[0] = -1\n",
    "        max_len = 0\n",
    "        \n",
    "        for index, num in enumerate(nums):\n",
    "            running_sum += num\n",
    "            if running_sum - k in hashmap:\n",
    "                max_len = max(max_len, index - hashmap[running_sum - k])\n",
    "            if running_sum not in hashmap:\n",
    "                hashmap[running_sum] = index\n",
    "                \n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        cumsum = [0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cumsum.append(cumsum[-1]+nums[i])\n",
    "        record = defaultdict(int)\n",
    "        max_length = 0\n",
    "        record[0] = 0\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if cumsum[i]-k in record:\n",
    "                max_length = max(max_length, i-record[cumsum[i]-k])\n",
    "            if cumsum[i] not in record:\n",
    "                record[cumsum[i]] = i\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        curSum = 0\n",
    "        # sum of a[0]...a[i], i.e. the first i elems: i\n",
    "        prefix = {0: 0}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            if curSum - k in prefix.keys():\n",
    "                # prefix[curSum - k]: j, means sum of the first j elems, i.e. a[0]...a[j-1], is prefix[curSum - k]\n",
    "                # sum of a[j]...a[i] is k. Length of the array is i - j + 1\n",
    "                res = max(res, i - prefix[curSum - k] + 1)\n",
    "            if curSum not in prefix.keys():\n",
    "                # curSum is the sum of the first i + 1 elems\n",
    "                prefix[curSum] = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSums = {}\n",
    "        curPreSum = 0\n",
    "        maxLen = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            curPreSum += num\n",
    "            target = curPreSum - k\n",
    "            if target == 0:\n",
    "                maxLen = max(maxLen, idx + 1)\n",
    "            elif target in preSums:\n",
    "                maxLen = max(maxLen, idx - preSums[target])\n",
    "            if curPreSum not in preSums:\n",
    "                preSums[curPreSum] = idx\n",
    "        \n",
    "        return maxLen\n",
    "\n",
    "'''\n",
    "k = 3\n",
    "[1,2,1]\n",
    "\n",
    "preSums = {0:0, 1:0}\n",
    "1, 2\n",
    "3, 0\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        sums = [0] * len(nums)\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                sums[0] = num\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + num\n",
    "            \n",
    "            if (t := sums[i] - k) in dist:\n",
    "                res = max(res, i - dist[t])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        hashmap = {}\n",
    "        running_sum = 0\n",
    "        hashmap[0] = -1\n",
    "        max_len = 0\n",
    "        \n",
    "        for index, num in enumerate(nums):\n",
    "            running_sum += num\n",
    "            if running_sum - k in hashmap:\n",
    "                max_len = max(max_len, index - hashmap[running_sum - k])\n",
    "            if running_sum not in hashmap:\n",
    "                hashmap[running_sum] = index\n",
    "                \n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = 0\n",
    "        ans = 0 \n",
    "        pre_sum_idx = {}\n",
    "        pre_sum_idx[0] = -1\n",
    "        for i in range(n):\n",
    "            pre_sum += nums[i]\n",
    "            if not pre_sum in pre_sum_idx:\n",
    "                pre_sum_idx[pre_sum] = i\n",
    "            \n",
    "            if pre_sum - k in pre_sum_idx:\n",
    "                ans = max(ans, i - pre_sum_idx[pre_sum - k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 创建一个字典，用于存储前缀和及其对应的下标\n",
    "        num2index = dict()\n",
    "\n",
    "        # 初始化最长子数组的长度为0\n",
    "        max_length = 0\n",
    "\n",
    "        # 初始化前缀和为0\n",
    "        prefix_sum = 0\n",
    "\n",
    "        # 遍历数组\n",
    "        for i in range(len(nums)):\n",
    "            # 计算当前的前缀和\n",
    "            prefix_sum += nums[i]\n",
    "\n",
    "            # 如果当前的前缀和等于目标值k，则更新最长子数组的长度\n",
    "            if prefix_sum == k:\n",
    "                max_length = i + 1  # 因为是从第一个元素开始的，所以长度是 i+1\n",
    "\n",
    "            # 检查当前前缀和减去目标值k是否在字典中\n",
    "            if prefix_sum - k in num2index.keys():\n",
    "                # 如果在字典中，说明找到了一个和为k的子数组\n",
    "                # 更新最长子数组的长度\n",
    "                max_length = max(max_length, i - num2index[prefix_sum - k])\n",
    "\n",
    "            # 如果当前的前缀和不在字典中，则将其添加到字典中\n",
    "            # 注意：我们只记录第一次出现该前缀和的下标\n",
    "            if prefix_sum not in num2index.keys():\n",
    "                num2index[prefix_sum] = i\n",
    "\n",
    "        # 返回找到的最长子数组的长度\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefixsum = 0\n",
    "        longest = 0\n",
    "        indices = {}\n",
    "        l = len(nums)\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        elif l == 1:\n",
    "            if nums[0] == k:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        for i in range(l):\n",
    "            prefixsum += nums[i]\n",
    "            if prefixsum == k:\n",
    "                if longest <= (i + 1):\n",
    "                    longest = i + 1\n",
    "            if prefixsum - k in indices:\n",
    "                index = indices[prefixsum - k]\n",
    "                if i - index >= longest:\n",
    "                    longest = i - index\n",
    "            if prefixsum not in indices:\n",
    "                indices[prefixsum] = i\n",
    "        return longest\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = 0\n",
    "        ans = 0 \n",
    "        pre_sum_idx = {}\n",
    "        pre_sum_idx[0] = -1\n",
    "        for i in range(n):\n",
    "            pre_sum += nums[i]\n",
    "            if not pre_sum in pre_sum_idx:   # important, always maitain the first occurance to ensure longest\n",
    "                pre_sum_idx[pre_sum] = i\n",
    "            \n",
    "            if pre_sum - k in pre_sum_idx:\n",
    "                ans = max(ans, i - pre_sum_idx[pre_sum - k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 创建一个字典，用于存储前缀和及其对应的下标\n",
    "        num2index = dict()\n",
    "\n",
    "        # 初始化最长子数组的长度为0\n",
    "        max_length = 0\n",
    "\n",
    "        # 初始化前缀和为0\n",
    "        prefix_sum = 0\n",
    "\n",
    "        # 遍历数组\n",
    "        for i in range(len(nums)):\n",
    "            # 计算当前的前缀和\n",
    "            prefix_sum += nums[i]\n",
    "\n",
    "            # 如果当前的前缀和等于目标值k，则更新最长子数组的长度\n",
    "            if prefix_sum == k:\n",
    "                max_length = i + 1  # 因为是从第一个元素开始的，所以长度是 i+1\n",
    "\n",
    "            # 检查当前前缀和减去目标值k是否在字典中\n",
    "            if prefix_sum - k in num2index.keys():\n",
    "                # 如果在字典中，说明找到了一个和为k的子数组\n",
    "                # 更新最长子数组的长度\n",
    "                max_length = max(max_length, i - num2index[prefix_sum - k])\n",
    "\n",
    "            # 如果当前的前缀和不在字典中，则将其添加到字典中\n",
    "            # 注意：我们只记录第一次出现该前缀和的下标\n",
    "            if prefix_sum not in num2index.keys():\n",
    "                num2index[prefix_sum] = i\n",
    "\n",
    "        # 返回找到的最长子数组的长度\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct = dict()\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        dct[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in dct and i - dct[pre - k] > ans:\n",
    "                ans = i - dct[pre - k]\n",
    "            if pre not in dct:\n",
    "                dct[pre] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        sums = [0] * len(nums)\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                sums[0] = num\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + num\n",
    "            \n",
    "            if (t := sums[i] - k) in dist:\n",
    "                res = max(res, i - dist[t])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        sums = [0] * n\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                sums[0] = nums[0]\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + nums[i]\n",
    "            \n",
    "            if sums[i] - k in dist:\n",
    "                res = max(res, i - dist[sums[i] - k])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            presum[i] = presum[i-1] + nums[i-1]\n",
    "        print(presum)\n",
    "        \n",
    "        # maxStr = 0\n",
    "        # for i in range(n+1):\n",
    "        #     for j in range(i, n+1):\n",
    "        #         if presum[j] - presum[i] == k:\n",
    "        #             maxStr = max(maxStr, (j-i))\n",
    "\n",
    "        # for i in range(n,-1,-1):\n",
    "        #     for j in range(0, n+1-i):\n",
    "        #         if presum[j+i] - presum[j] == k:\n",
    "        #             return i\n",
    "        maxStr = 0\n",
    "        d = {}\n",
    "        for i in range(1, n+1):\n",
    "            if presum[i] == k:\n",
    "                maxStr = i\n",
    "            if (presum[i] - k) in d:\n",
    "                maxStr = max(maxStr, i - d[presum[i] - k])\n",
    "            if presum[i] not in d:\n",
    "                d[presum[i]] = i\n",
    "            \n",
    "        return maxStr\n",
    "            \n",
    "        return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        d = {}\n",
    "        pre = 0\n",
    "        longest = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            pre += num\n",
    "            if pre == k:\n",
    "                longest = i+1\n",
    "            if pre-k in d:\n",
    "                longest = max(longest, i-d[pre-k])\n",
    "            if pre not in d:\n",
    "                d[pre] = i\n",
    "        return longest\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)==1:\n",
    "            if k==nums[0]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        line=[0]\n",
    "        for idt in range(len(nums)-1):\n",
    "            line.append(line[-1]+nums[idt])\n",
    "\n",
    "        d=set([0])\n",
    "        dic={0:0}\n",
    "        if k in nums:\n",
    "            length=1\n",
    "        else:\n",
    "            length=float(\"-inf\")\n",
    "        for idt in range(len(nums)):\n",
    "            b=line[idt]\n",
    "            x=nums[idt]\n",
    "            if b+x-k in d:\n",
    "                length=max(length,idt-dic[b+x-k]+1)\n",
    "            if b not in d:\n",
    "                d.add(b)\n",
    "                dic[b]=idt\n",
    "        if length==float(\"-inf\"):\n",
    "            return 0\n",
    "        return length\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        len_n = len(nums)\n",
    "        prefix_dict = defaultdict(list)\n",
    "        prefix_dict[0].append(0)\n",
    "        prefix_dict[nums[0]].append(1)\n",
    "\n",
    "        for idx in range(1,len_n):\n",
    "            nums[idx] += nums[idx-1]\n",
    "            prefix_dict[nums[idx]].append(idx+1)\n",
    "\n",
    "        max_gap = 0\n",
    "        for key in prefix_dict.keys():\n",
    "            if key + k not in prefix_dict:\n",
    "                continue\n",
    "            vals1 = prefix_dict[key]\n",
    "            vals2 = prefix_dict[key+k]\n",
    "            max_gap = max(max_gap, vals2[-1] - vals1[0])\n",
    "\n",
    "        print(prefix_dict)\n",
    "        return max_gap\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefixSum = {0:[-1]}\n",
    "        curr = 0\n",
    "        for i in range(len(nums)):\n",
    "            curr += nums[i]\n",
    "            if curr in prefixSum:\n",
    "                prefixSum[curr].append(i)\n",
    "            else:\n",
    "                prefixSum[curr] = [i, ]\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            require = s - k\n",
    "            if require in prefixSum:\n",
    "                ans = max(ans, i - prefixSum[require][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        presum = [0] * (len(nums) + 1)\n",
    "        for i, n in enumerate(nums):\n",
    "            presum[i + 1] = presum[i] + n\n",
    "\n",
    "        presum_dict = dict()\n",
    "        max_l = 0\n",
    "        for i, p in enumerate(presum):\n",
    "            \n",
    "            if p - k in presum_dict:\n",
    "                for m in presum_dict[p - k]:\n",
    "                    max_l = max(max_l, i - m)\n",
    "\n",
    "            presum_dict[p] = presum_dict[p] + [i] if p in presum_dict else [i]\n",
    "\n",
    "        return max_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        self.hashMap = collections.defaultdict(lambda:-1)\n",
    "        n = len(nums)\n",
    "        pre_sum = [0]*(n+1)\n",
    "        self.hashMap[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            pre_sum[i]=pre_sum[i-1]+nums[i-1]\n",
    "            if self.hashMap[pre_sum[i]] == -1:\n",
    "                self.hashMap[pre_sum[i]]=i\n",
    "        #print(self.hashMap)\n",
    "        max_len = 0\n",
    "        for i in range(1,n+1):\n",
    "            idx = self.hashMap[pre_sum[i]-k] \n",
    "            if idx!=-1 and idx<i:\n",
    "                max_len = max(max_len,i-idx)\n",
    "        \n",
    "        return max_len"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
